1. Technical Field
The invention relates to computers. More particularly, the invention relates to computer implemented integer operations.
2. Description of Prior Art
While most integer operations can be performed by a computer in a single processor cycle, such operations as multiplies usually require three or more cycles to finish. Thus, multiplying integer numbers is a relatively expensive operation to perform on modern computers.
On some computer architectures, no integer multiply operation is provided by the arithmetic-logic unit (ALU) and multiply operations must either be performed as a long sequence of shifts, adds, and subtracts (much like a person would perform long multiplication by hand); or by transferring the integer values to the floating-point unit (FPU) and performing the multiply operation there. Because of this, code improvement transformations that compilation systems can automatically perform to eliminate multiplies or reduce their cost are important.
A number of approaches have been described and implemented to reduce the cost of multiply operations. Perhaps the oldest and most-commonly implemented schemes are algebraic transformations that remove multiplies where one of the multipliers is known to be either zero (the product is then also zero) or one (the product is then the same value as the other multiplier). Equally ubiquitous are constant folding transformations that replace a multiply whose multipliers are both known constant values with a cheaper code sequence instantiating the appropriate product value.
Also well known are transformations that replace multiplications where one of the multipliers is a known power of 2 (e.g. 2, 4, 8, or 16) with a "left-shift" operation that shifts each bit of the unknown multiplier by the base 2 logarithm of the known multiplier value to yield the desired product. This simple observation can be combined with addition and subtraction to transform multiplies where one of the multipliers is a known constant value to a faster sequence of shift, add, and subtract instructions (see, for example R. Bernstein, Multiplication by Integer Constants, Software-Practice And Experience, Vol. 16(7), pp. 641-652 (1986)).
Finally, in cases where the values of both multipliers are unknown at the time that the source code is processed by the compilation system and a fast floating-point multiply operation is available on the target architecture, the integer multiply can be transformed into a code sequence that converts the integer multipliers to appropriate floating-point values, multiplies the floating-point values to produce a floating-point product, and then converts this value back to its integer representation.
It would be advantageous to provide a technique that increases the cases where a compilation system for a computer that performs relatively slow multiplication operations can improve the performance of the compiled code.